package com.arron.algorithm.leetcodetop100.动态规划;

import com.sun.org.apache.bcel.internal.generic.RET;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 回溯解法：
 *
 * @see com.arron.algorithm.leetcodetop100.回溯.单词拆分
 */
public class 单词拆分II {


    Set<String> wordDictSet;
    List<String> res;


    public List<String> wordBreak(String s, List<String> wordDict) {

        wordDictSet = new HashSet<>(wordDict);
        res = new ArrayList<>();
         matchPrefix(s, 0,new ArrayList<>());
         return res;
    }

    public void matchPrefix(String s, int start,List<String> strList) {



        if (start == s.length()) {
            String s1 = String.join(" ", strList);
            res.add(s1);
        }


        for (int len = 1; len <= s.length()-start; len++) {

            String prefix = s.substring(start, start + len);
            if (wordDictSet.contains(prefix)) {
                strList.add(prefix);
                matchPrefix(s, start + len,strList);
                strList.remove(strList.size()-1);
            }
        }

    }




    public static void main(String[] args) {
        String s = "aaaaaab";
        List<String> strings = new ArrayList<>(Arrays.asList("a","aa","aaa","aaaa","aaaaa","aaaaaa","b"));

        单词拆分II wordBreak = new 单词拆分II();
        System.out.println(wordBreak.wordBreak(s, strings));

    }


}
